/*
 * Created on 15 avr. 2005 by Tudor.Ionescu@supelec.fr
 */
package clustering.implementations;
import clustering.framework.*;
import clustering.testing.Debug;

import org.w3c.dom.*;

import java.util.*;
/**
 * @author Tudor.Ionescu@supelec.fr

QuartetTreeScorer

This class is an implementation of the tree scoring method from the Vitanyi-Cilibrasi quartet method. It is based on the calculation of the costs of all the consistent quartet topologies which can be found in a given phylogenetic tree.

 */
public class QuartetTreeScorer implements IClusterTreeScorer{
    QNode [] qNodes = null;
    Hashtable htPath = null;
    public ArrayList consistentQuartets = null;
    public boolean isOptimal(Quartet q, double [][] dm)
    {
    	double cost = q.weight;
    	double cost2 = min(cost,dm[q.nodes[0]][q.nodes[2]]+dm[q.nodes[1]][q.nodes[3]],dm[q.nodes[0]][q.nodes[3]]+dm[q.nodes[1]][q.nodes[2]]); 
    	if(cost == cost2)
    	{
    		return true;
    	}
    	return false;
    }
    static double min(double a, double b, double c){
        if(a <= b && a <= c)return a;
        else if(b <= a && b <= c)return b;
        else return c;
    }
    static double max(double a, double b, double c){
        if(a >= b && a >= c)return a;
        else if(b >= a && b >= c)return b;
        else return c;
    }
    
    public double ComputeScore(Document xmlTree, double [][] dMatrix){
        qNodes = new QNode[2*dMatrix.length-2];
        ArrayList alQuartets = Quartet.generate3FullQuartetList(dMatrix);
        QuartetTree qt = constructFromXmlDocument(xmlTree);
        qt.M = Quartet.worst_cost.doubleValue();
        qt.m = Quartet.best_cost.doubleValue();
        int consistent = 0;
        htPath = new Hashtable();
        consistentQuartets = new ArrayList();
        double Ct = 0;
        int count_optimal = 0;
        for(int i=0;i<alQuartets.size();i++){
            Quartet q = (Quartet)alQuartets.get(i);
            if(isConsistent(q,qt)){
                Ct += q.weight;
                consistent++;
                consistentQuartets.add(q);
                if(isOptimal(q,dMatrix))count_optimal++;
            }
        }
        double score = (qt.M - Ct)/(qt.M - qt.m);
        if(consistent != alQuartets.size()/3){
        	//throw new Exception("Inconsistent quartet tree:"+consistent+"/"+alQuartets.size());
        	Debug.append("Inconsistent tree with score: "+score);
        }            
        return count_optimal;
    }
    int node_count;
    QuartetTree constructFromXmlDocument(Document xmlTree){
        QuartetTree qt = new QuartetTree();
        QNode qn = new QNode(-1,null,null,null,-1);
        Node xmlNode = xmlTree.getFirstChild();
        node_count = 0;
        for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
			generateTree(xmlNode.getChildNodes().item(i),qn);
		}
        if(xmlNode.getChildNodes().getLength()==2){
		    QNode n1 = qn.adj[0];
		    QNode n2 = qn.adj[1];
		    n1.adj[0] = n2;
		    n2.adj[0] = n1;
		    qt.root = n1;
		}else{
		    qNodes[node_count++]=qn;
		    qt.root = qn;
		}        
        return qt;
    }
    void generateTree(Node xmlNode, QNode n0){
        String sId = xmlNode.getAttributes().getNamedItem("id").getNodeValue();
		int id = Integer.parseInt(sId);
		QNode qn = new QNode(id,n0,null,null,-1);
		if(n0.adj[0]==null)n0.adj[0]=qn;
		else if(n0.adj[1]==null)n0.adj[1]=qn;
		else n0.adj[2]=qn;
		if(xmlNode.hasChildNodes()){
			for(int i=0;i<xmlNode.getChildNodes().getLength();i++){
				generateTree(xmlNode.getChildNodes().item(i),qn);
			}			
		}
		qNodes[node_count++]=qn;
	}
    boolean isConsistent(Quartet q, QuartetTree qt){
        QNode a = getNodeByLabel(q.nodes[0]);
        QNode b = getNodeByLabel(q.nodes[1]);
        QNode c = getNodeByLabel(q.nodes[2]);
        QNode d = getNodeByLabel(q.nodes[3]);
        if(htPath.get(a)==null){
        	htPath.put(a,qt.Dijkstra(a,qNodes));
        }
        if(htPath.get(b)==null){
        	htPath.put(b,qt.Dijkstra(b,qNodes));
        }
        if(htPath.get(c)==null){
        	htPath.put(c,qt.Dijkstra(c,qNodes));
        }
        if(htPath.get(d)==null){
        	htPath.put(d,qt.Dijkstra(d,qNodes));
        }
        ArrayList path1 = (ArrayList)((Hashtable)htPath.get(a)).get(b);
        ArrayList path2 = (ArrayList)((Hashtable)htPath.get(c)).get(d);
        for(int i=1;i<path1.size()-1;i++){
            QNode qn1 = (QNode)path1.get(i);
            for(int j=1;j<path2.size()-1;j++){
                QNode qn2 = (QNode)path2.get(j);
                if(qn1 == qn2)return false;
            }
        }
        return true;
    }
    QNode getNodeByLabel(int label){
        for(int i=0;i<qNodes.length;i++){
            QNode qn = qNodes[i];
            if(qn.label == label)return qn;
        }
        return null;
    }
}
